/**
 * @param {number[]} heights
 * @return {number}
 */

var largestRectangleArea = function (heights) {
    // 缓存柱子高度的数量
    const len = heights.length
    // 判断边界条件
    if (!heights || !len) return 0
    // 初始化最大值
    let max = -1
    // 初始化栈
    const stack = []
    // 开始遍历
    for (let i = 0; i < len; i++) {
        // 如果栈已经为空或当前柱子大于等于前一个柱子的高度
        if (!stack.length || heights[i] >= heights[stack[stack.length - 1]]) {
            // 执行入栈操作
            stack.push(i)
        } else {
            // 矩形的右边界
            let right = i
            // pop出作为计算目标存在的那个柱子
            let target = stack.pop()
            // 处理柱子高度相等的特殊情况
            while (stack.length && heights[target] === heights[stack[stack.length - 1]]) {
                // 若柱子高度相等，则反复pop
                target = stack.pop()
            }
            // 矩形的左边界
            let left = (!stack.length) ? -1 : stack[stack.length - 1]
            // 左右边界定宽，柱子定高，计算矩形面积
            max = Math.max(max, (right - left - 1) * heights[target])
            // 这一步保证下一次循环从当前柱子往下走（因为当前柱子还没作为计算目标计算出结果）
            i--
        }
    }
    // rightAdd是我们针对右边界为空这种情况，补上的一个假的右边界
    let rightAdd = stack[stack.length - 1] + 1
    // 此时栈里是高度单调递增（不减）的柱子索引，这些柱子还没有参与计算，需要针对它们计算一遍
    while (stack.length) {
        // 取出栈顶元素作为计算目标
        let target = stack.pop()
        // 找到左边界
        let left = (!stack.length) ? -1 : stack[stack.length - 1]
        // 注意这里的右边界一定是rightAdd，想一想，为什么？
        max = Math.max(max, (rightAdd - left - 1) * heights[target])
    }
    // 返回计算出的最大值
    return max
};